package com.zhu.algorithm.sort;

import com.zhu.algorithm.sort.impl.Sort;

import java.util.Arrays;

/*算法步骤
从数列中挑出一个元素，称为 “基准”（pivot）;

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
*
* */
/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zhujiabao
 * @Date: 2021/12/27/18:55
 * @Description:快速排序
 */
public class QuickSort implements Sort {

    @Override
    public int[] sort(int[] sourceArray) {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        long A=System.currentTimeMillis();

        quick(arr,0,arr.length-1);

        long B=System.currentTimeMillis();
        System.out.println("快速排序所耗时间： "+(B-A)+"ms");

        return arr;
    }

    /**
     * 快速排序
     * @param arr
     * @param left
     * @param right
     */
    private void quick(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        // 设定基准值（pivot）
        int pivot = arr[right];
        int i = left;
        for (int j = left; j <= right; j++) {
            if (j == right) {
                swap(arr, i, right);
                break;
            }
            if (arr[j] < pivot) {
                swap(arr, i, j);
                i++;
            }
        }

        // 左
        quick(arr, left, i-1);

        // 右
        quick(arr, i+1, right);
    }


/*
    private void quick(int[] arr,int left,int right){
        if (left > right || arr.length < 2)
            return;
        // 设定基准值（pivot）
        int pivot = arr[left];
        int i = left;
        int j = left+1;
        while (j<=right){
            if (arr[j] >= pivot)
                j++;
            else {
                swap(arr,++i,j);
                j++;
            }
        }
        if (i != left) {
            swap(arr, left, i);
        }

        //左半部分的数组
        quick(arr,left,i-1);
        //右半部分的数组
        quick(arr,i+1,right);
    }*/

    private void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
